package com.lun.swordtowardoffer2.c12;

import java.util.Random;

public class FindKthLargest {

	public int findKthLargest(int[] nums, int k) {
		int target = nums.length - k;
		int start = 0, end = nums.length - 1;
		int pivotIndex = partition(nums, start, end);
		while(pivotIndex != target) {
			if(target < pivotIndex) {
				end = pivotIndex - 1;
			}else {
				start = pivotIndex + 1;
			}
			
			pivotIndex = partition(nums, start, end);
		}
		return nums[pivotIndex];
	}
	
	private int partition(int[] nums, int start, int end) {
		int rand = new Random().nextInt(end - start + 1);
		swap(nums, start + rand, end);
		
		int pivotIndex = start - 1;
		 
		for(int i = start; i < end; i++) {
			if(nums[i] < nums[end]) {
				pivotIndex++;
				swap(nums, pivotIndex, i);
			}
		}
		
		pivotIndex++;
		swap(nums, pivotIndex, end);
		
		return pivotIndex;
	}
	
	private void swap(int[] nums, int i, int j) {
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
}
